#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<vector<int> > combinationSum(vector<int> &candidates, int target);

int main(int argc, char **argv){

    vector<int> cand;
    cand.push_back(2);
    cand.push_back(3);
    cand.push_back(6);
    cand.push_back(7);
    combinationSum(cand, 7);

    return 0;
}

vector<vector<int> > combinationSum(vector<int> &candidates, int target) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    sort(candidates.begin(), candidates.end());
    vector<set<vector<int> > > comb;
    set<vector<int> > empty;
    comb.push_back(empty);
    for(int i=1; i<=target; ++i){
        set<vector<int> > levelSet;
        for(vector<int>::iterator it= candidates.begin();
            it != candidates.end();
            ++it){
            if(*it>i){
                break;
            }
            if(*it==i){
                vector<int> tmp;
                tmp.push_back(i);
                levelSet.insert(tmp);
            }
            else{
                for(set<vector<int> >::iterator iit=comb[i-*it].begin();
                    iit != comb[i-*it].end();
                    ++iit){
                    vector<int> tmp(*iit);
                    tmp.push_back(*it);
                    sort(tmp.begin(), tmp.end());
                    levelSet.insert(tmp);
                }
            }
        }
        comb.push_back(levelSet);
    }
    // output
    vector<vector<int> > res;
    for(set<vector<int> >::iterator it = comb[target].begin();
        it != comb[target].end();
        ++it){
        res.push_back(*it);
    }

    return res;
}





